A Forward Solution of LeetCode 991. Broken Calculator

Problem description

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 10^9
1 <= Y <= 10^9

Solution (Forward)

The solution which to think in the backward is trivial, and it is LeetCode’s official solution.
But it did take me some time to work out the forward solution of my own.

Python3 Code:

class Solution:
    def brokenCalc(self, X: int, Y: int) -> int:
        if Y <= X:
            return X - Y
        total = 0
        while X < Y:
            X *= 2
            total += 1

        diff = X - Y
        back_n_steps = total
        while diff > 0 and back_n_steps > 0:
            if diff & 1 == 1:
                total += 1
            diff = diff // 2
            back_n_steps -= 1
        return total + diff

Basic Ideas

1. The effect of decrement in earlier stages can be propgated to later stages;
2. The only way to increase X is to double it, so we have to keep double X until it is >= Y;
3. So we can encode the effect of decrement in binary. The total number of 1 bits in the binary int means How many decrements we had to perform in the earlier stages;
4. Times of doubling + Times of decrements = total Ops

Definition of the stage: a pair of operations (-1, *2). (-1) is always performed before (*2), if (-1) is required.

---

Example

X = 3, Y = 13

1. Firstly, double X for 3 times, we have X = 24;
   • The current operations are: (*2), (*2), (*2)
2. The difference X - Y = 11 —> In binary, 11 = b1011
3. b1011 indicates we need to decrease in 1st, 3rd, 4th stages (nth from leftmost bit to the right)
4. We can modify the operations according to the above result:
   • Modiy Ops as (-1, *2); (*2), (-1, *2), (-1)
5. With the ops in 4, we can have :
   5.1. X = X - 1 = 2
   5.2. X = X 2 = 2 2 = 4
   5.3. X = X 2 = 4 2 = 8
   5.4. X = X - 1 = 8 - 1 = 7
   5.5. X = X 2 = 7 2 = 14
   5.6. X = X - 1 = 13
6. In total, we have 6 operations to get Y=13 from X=3, which gives us the best answer.

---

Important Edgecase

Reader may noticed the back_n_steps variable in the Python3 code, why do we need it?

Consider this test case: X = 68, Y = 71

If we follow the steps in Example section, we will have b1000001 in the 2/3 step.

What’s the problem here? Should we simply decrease 1 in the 1st and last stages?

WE DON’T HAVE THAT MANY STAGES!

The X is only doubled 1 time to 136 then it is greater than Y=71, which means we really cannot decrese 1 in the 1st (or if look backwardly, 7th old stage) —> the stage doesn’t exist at all.

So what does b1000001 means? It actually means:

1. minus b1000000=32 before the very first (*2) op
2. do a final (-1) at the very end

In this case, we don’t have old enough stages to let the effect of (-1) grows, so we have to manually decre it to the target…

Operation sequence in this case should be:

1. 68 - 1 * 32 = 36
2. 36 * 2 = 72
3. 72 - 1 = 71

Total: 32 + 1 + 1 = 34 ops